This invention relates to digital processing systems and, more particularly, to a method and means utilizing data processing means for determining the degree of match between two data arrays.
Data processing methods and means are known for processing data arrays. Method and means of this type are also known which look for a match between one data array, hereinafter called "query" and a "stored data base array".
One such method and means is disclosed in a Belgium application No. 195,432, entitled "Data Processor Method And Means For Determining Degree Of Match Between Two Data Arrays", that issued as Belgian Pat. No. 876,591 on Nov. 28, 1979. The Belgian application, filed in the name of the same assignee as this application, is directed to and discloses a way of processing a priorly formed array of data values. The data values represent the number of shift positions required of a query event for the juxtaposition of such query event with a like event in a stored data base. The data values are stored in a storage device that contains a plurality of chute stores and a temporary stored called a "pocket", for each chute.
In processing the array of data values, the chutes are "emptied" for determining that relative juxtaposition of the events of a query and the events of a stored data base in which the sum of the number of locations between all like events is a minimum.
A U.S. Pat. No. 4,068,298 discloses a method and means using concepts called "piping" and "brightness" to locate those entries in each layer of a stored multi-layer data base which have a predetermined degree of match, i.e., brightness to a query. Event times or "time ticks" are used to represent the order of occurrence of events and entries (composed of events) making up each layer of the data base.
Utilizing the time ticks, the method and means determine those stored data base entries which have a predetermined degree of match with the query. The number of event positions of displacement between an event of the query and a corresponding (like) event in a data base is used in determining the predetermined degree of match. As a result, exact and inexact retrievals of data from the stored data base are more easily, efficiently, and rapidly achieved.
The above-referenced application titled, "Method and Means Utilizing Multiple Processing Means for Determining Degree of Match Between Two Data Arrays" is broadly directed to an improved method and means utilizing data processing means to aid in the process of rapidly and efficiently determining the degree of match between a query array and a stored data base array. The application discloses method and means which operate on or utilize a priorly formed array of data values. Each data value represents the number of event positions between the occurrence of events in the query and the occurrence of corresponding events in the stored data base. The method and means use the priorly formed array of data values to rapidly and efficiently process and determine the position or entry in the stored data base which has the best match with the query and importantly forms a criterion value. The criterion value relates to the brightness or degree of match between the query and the identified entry in the stored data base.
The above-referenced application also mentions the concept of interrogating a layered data base by means of brightness propagaton and package piping. Moreover, this is the invention of the present inventor.
This application is directed to and discloses a method and means for interrogating a layered data base by means of brightness propagation and package piping. The concept of brightness propagation utilizes the brightness values formed on one layer of a data base as a weighting value accompanying the just formed array of data values for piping on a next higher layer. When one does not propagate brightness between layers, the query events selected are handled as if their event types had been exact matches with the stored data base on a lower layer. Thus, for inexact retrievals creating more than just a few possible intermediate queries, much valuable query information is lost. And, for the intermediate queries that are used, the assumption that they are the result of exact matches on a lower layer causes the interrogation method to place improper emphasis on matching higher layer events.
The method and means described in the prior patent that utilize non-package piping of the events of a query require that each query event grouping represented in a package query be piped separately. Thus, the total number of calculations required equals the total number of calculations needed to form the array of data values and process the array of data values to form a criterion value. The present invention provides significant advantage in that in utilizing the package piping method, the amount of calculations required in processing the array of data values is significantly reduced and in utilizing brightness propagation between layers, the amount of unrelated retrievals in response to a system request is also significantly reduced.